import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// https://leetcode.cn/problems/combination-sum/
public class CombinationSum {
    class Solution {
        private List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            Arrays.sort(candidates);
            backTracking(new ArrayList<>(),0,candidates,target);
            return res;

        }

        private void backTracking(List<Integer> path , int start , int [] candidates , int sum)
        {
            if(sum == 0)
            {
                res.add(new ArrayList<>(path));
                return ;
            }
            for(int i = start ; i < candidates.length && candidates[i] <= sum ; i ++)
            {
                path.add(candidates[i]);
                backTracking(path,i,candidates,sum - candidates[i]);
                path.remove(path.size()-1);
            }

        }
    }
}
